栈和队列——生成窗口最大值数组

Posted on | In ,

题目：
输入：整型数组arr，长度为n，窗口大小为w。（顺序移窗，则一共产生n-w+1个窗）
输出：一个长度为n-w+1的数组rst，rst[i]表示每种窗口状态下的最大值。如
int[] arr = {4,3,5,4,6,3,3,6,7},数组长为7，窗口w=3，则int[] rst = {5，5,5,6,4,7}

实现：利用（双端）队列qmax实现窗口最大值的更新，双端队列qmax中存放数组arr的下标。每个下标最多进一次，出一次，所有遍历过程中进出队列的时间复杂度为O(N)，整体时间复杂度也为O(N)。

  1. 开始时，qmax={}.
  2. 遍历到arr[0]=4，将下标0放入qmax，qmax={0}。
  3. 遍历到arr[1]=3,队尾下标为0，而arr[0]>arr[1]，将下标1放入qmax，qmax={0,1}。
  4. 遍历到arr[2]=5,队尾下标为1，而arr[1]<arr[2]（有比队尾大的元素，则删除队尾元素，直到5<队尾元素），因此将下标2弹出，qmax={0}。队尾下标为0，而arr[0]<arr[2]，因此将下标0弹出，qmax={}。将arr[2]写入，qmax={2}。
  5. 此时已经遍历到窗口arr[0…2]出现，当前qmax队头下标为2，所以窗口arr[0…2]的最大值为arr[2]。
  6. 遍历到arr[3]，当前队尾下标为2，arr[2]>arr[3]，因此将3压入，qmax={2,3}，
    此时窗口[1,…3]出现，当前队头下标为2，所以窗口arr[1,…3]的最大值为arr[2]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
public class GetMaxWindow {
	public static int[] getMaxWindow(int[] arr, int w) {
		if (arr == null || w < 1 || arr.length < w) {
			return null;
		}
		//创建队列，实现窗口最大值下标的更新
		LinkedList<Integer> qmax = new LinkedList<>();
		//rst数组用来存放窗口的最大值
		int[] rst = new int[arr.length - w + 1];
		int index = 0;
		//遍历数组arr，实现窗口最大值的更新
		for (int i = 0; i < arr.length; i++) {
			//只要存在比队尾大的元素，则删除队尾元素
			while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
				qmax.pollLast();
			} //直到arr[qmax.peekLast()] > arr[i]，则直接在队尾添加当前下标
			qmax.addLast(i);
			//当前下标i>=w-1则开始将qmax队首的arr数组元素下标弹出，
			//并将arr相应的数组值依次放入rst数组
			if (i >= w - 1) { 
				rst[index++] = arr[qmax.pollFirst()];
			}
		}
		return rst;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
	//Test
	public static void main(String[] args) {
		/*int[] arr = {4, 3, 5, 4, 3, 3, 6, 7};
		int w = 3;*/
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int w = sc.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++){
			arr[i] = sc.nextInt();
		}
		int[] result = getMaxWindow(arr, w);
		for (int i = 0; i < result.length; i++) {
			System.out.print(result[i] + " ");
		}
	}
}